package com.mccken.practice.top100.Top_1$20.top_10;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 76. 最小覆盖子串
 * <p>
 * 思路： 滑动窗口
 * <p>
 * 伪代码：
 * 1. 构建 map
 * 2. 遍历 s，维护一个window
 * 3. 通过valid来判断值
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-02 10:25
 **/
public class MinWindow {

	public String minWindow(String s, String t) {

		int len_s = s.length();
		int len_t = t.length();

		Map<Character, Integer> need = new HashMap<>();
		for (int i = 0; i < len_t; i++) {
			need.merge(t.charAt(i), 1, Integer::sum);
		}

		Map<Character, Integer> window = new HashMap<>();
		int left = 0, right = 0, valid = 0, start = 0, min = Integer.MAX_VALUE;

		while (right < len_s) {

			char right_value = s.charAt(right);
			right++;
			if (need.containsKey(right_value)) {
				window.merge(right_value, 1, Integer::sum);
				if (need.get(right_value).equals(window.get(right_value))) {
					valid++;
				}
			}

			while (valid == need.size()) {

				if (left < right) {
					char left_value = s.charAt(left);

					if (right - left < min) {
						min = right - left;
						start = left;
					}

					left++;

					if (need.containsKey(left_value)) {
						if (need.get(left_value).equals(window.get(left_value))) {
							valid--;
						}
						window.merge(left_value, -1, Integer::sum);
					}
				}
			}
		}
		
		if (min==Integer.MAX_VALUE) {
			return "";	
		} else {
			return s.substring(start, start+min);
		}

	}

	/**
	 * 太复杂了， 需要再写一遍
	 *
	 * @param s
	 * @param t
	 * @return
	 */
	public String minWindow2(String s, String t) {

		int len_s = s.length();
		int len_t = t.length();

		if (len_s < len_t) {
			return "";
		}
		Map<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < len_t; i++) {
			map.merge(t.charAt(i), 1, Integer::sum);
		}

		Map<Character, Integer> window = new HashMap<>();
		int valid = 0;
		int left = 0, right = 0, min = Integer.MAX_VALUE;
		Map<Integer, Integer> index_map = new HashMap<>();
		while (right < len_s) {
			char right_value = s.charAt(right);
			right++;

			// 窗口扩张时候，就判断valid
			if (map.containsKey(right_value)) {
				window.merge(right_value, 1, Integer::sum);
				if (map.get(right_value).equals(window.get(right_value))) {
					valid++;
				}
			}

			// 缩小窗口
			while (valid == map.size() && left < right) {
				char left_value = s.charAt(left);
				min = Math.min(min, right - left);

				index_map.putIfAbsent(min, left);
//				Integer needIndex = index_map.get(min);
//				String res = needIndex == null ? "" : 
				System.out.println(s.substring(left, right));

				left++;

				if (map.containsKey(left_value)) {
					if (map.get(left_value).equals(window.get(left_value))) {
						valid--;
					}
					window.merge(left_value, -1, Integer::sum);
				}
			}
		}

		Integer needIndex = index_map.get(min);
		String res = needIndex == null ? "" : s.substring(needIndex, needIndex + min);
		return res;
	}

	public String minWindow1(String s, String t) {

		int len_s = s.length();
		int len_t = t.length();

		if (len_s < len_t) {
			return "";
		}

		Map<Character, Integer> map = new HashMap<>();

		for (int i = 0; i < len_t; i++) {
			map.merge(t.charAt(i), 1, Integer::sum);
		}

		Map<Character, Integer> window = new HashMap<>();
		int valid = 0;
		int left = 0, right = 0;
		Integer min = Integer.MAX_VALUE;
		Queue<Character> queue = new LinkedList<>();
		String res = "";
		while (right < len_s) {
			char right_value = s.charAt(right);
			queue.offer(right_value);
			right++;

			window.merge(right_value, 1, Integer::sum);

			if (map.containsKey(right_value) && map.get(right_value).equals(window.get(right_value))) {
				valid++;
			}

			while (left < right && (valid == map.size() || right == len_s)) {
				if (valid == map.size()) {
					char left_value = s.charAt(left);
					StringBuilder sb = new StringBuilder();
					queue.forEach(sb::append);
					min = Math.min(min, sb.length());
					if (min == sb.length()) {
						res = sb.toString();
						System.out.println(res);
					}
					queue.poll();
					if (valid > 0 && map.containsKey(left_value) && map.get(left_value).equals(window.get(left_value))) {
						valid--;
					}
					window.merge(left_value, -1, Integer::sum);
					left++;
				}

				if (right == len_s) {
					char left_value = s.charAt(left);
					StringBuilder sb = new StringBuilder();
					queue.forEach(sb::append);
					min = Math.min(min, sb.length());
					if (min == sb.length()) {
						res = sb.toString();
						System.out.println(res);
					}
					queue.poll();

					window.merge(left_value, -1, Integer::sum);
					if (valid > 0 && map.containsKey(left_value) && map.get(left_value).equals(window.get(left_value))) {
						valid--;
					}
					left++;
				}

			}

		}

		return res;
	}

	public static void main(String[] args) {
		Deque<Character> queue = new LinkedList<>();
		queue.addLast('a');
		queue.addLast('b');
		queue.addLast('c');
		queue.removeFirst();
		StringBuilder sb = new StringBuilder();
		queue.forEach(item -> sb.append(item));

//		System.out.println(sb);

		MinWindow minWindow = new MinWindow();
//		System.out.println(minWindow.minWindow("ADOBECODEBANC", "ABC"));
//		System.out.println(minWindow.minWindow("a", "a"));
		System.out.println(minWindow.minWindow("cabwefgewcwaefgcf", "cae"));
	}
}
